package com.ztom.top100;

/**
 * 最长有效括号
 * <p>
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 *
 * @author ZhangTao
 */
public class Code16LongestValidParentheses {

    public int longestValidParentheses1(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[] max = {0};
        // 末尾是 '(' 的跳过
        int i = str.length - 1;
        while (i >=0 && str[i] == '(') {
            i--;
        }
        if (i < 0) {
            return 0;
        }
        process(str, i, max);
        return max[0];
    }

    private int process(char[] str, int index, int[] max) {
        if (index == 0) {
            // 以 0 位置结尾的有效长度一定是 0
            return 0;
        }
        if (index == 1) {
            // 以 1 结尾
            int curLen = str[0] == '(' && str[1] == ')' ? 2 : 0;
            max[0] = Math.max(max[0], curLen);
            return curLen;
        }
        // 以 index 位置结尾的有效括号长度, index 位置必须是 ')'
        if (str[index] == ')') {
            // 考察 index 位置减去前一位置的有效长度的再前一个位置
            int preLen = process(str, index - 1, max);
            int pre = index - preLen - 1;
            if (pre >= 0 && str[pre] == '(') {
                int curLen = preLen + 2;
                // pre 位置的前一个位置可能存在有效括号
                if (pre > 0) {
                    curLen += process(str, pre - 1, max);
                }
                max[0] = Math.max(max[0], curLen);
                return curLen;
            }
        } else {
            process(str, index - 1, max);
        }
        return 0;
    }

    public int longestValidParentheses(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }
        char[] str = s.toCharArray();
        int max = 0;
        // 以 i 位置结尾, 最长有效括号长度
        int[] dp = new int[str.length];
        for (int i = 1; i < str.length; i++) {
            if (str[i] != ')') {
                continue;
            }
            // i 位置是 ')'
            // 考察前一位的有效长度, 当前位置减去有效长度前面的位置 匹配
            int pre = i - dp[i - 1] - 1;
            // 如果 pre 存在且是 '('
            if (pre >= 0 && str[pre] == '(') {
                dp[i] = dp[i - 1] + 2;
                // pre 前面还可能存在有效的括号
                if (pre > 0) {
                    dp[i] += dp[pre - 1];
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}
